1. Technical Field
The present invention relates to cache memories in general, and, in particular, to an apparatus for implementing a Least-Recently Used (LRU) cache line replacement scheme in a cache memory. Still more particularly, the present invention relates to an apparatus for implementing an LRU cache line replacement scheme in a multi-port cache memory within a data processing system.
2. Description of the Related Art
A data processing system typically includes both a system memory and a cache memory. A cache memory is a small and relatively high-speed memory interposed between a processor and the system memory. Information such as data or instructions may be copied from a portion of the system memory into the cache memory so that the information will be available to the processor in a relatively short amount of time when the requested information resides in the cache memory.
However, if the information requested by the processor cannot be found in the cache memory (i.e., a cache miss), the requested information must be obtained from the system memory. After the information has been obtained from the system memory, a copy of the information may also be placed in the cache memory for future usage, in addition to the immediate usage by the processor. Thus, when all possible storage locations for the information within the cache memory are completely filled, some of the information already stored in the cache memory has to be replaced by the new information via an operation known as linefill. Needless to say, it is important to have a strategy to decide what specific information already stored in the cache memory needs to be discarded in order to make room for the new information. Generally speaking, a Least-Recently Used (LRU) replacement scheme is typically employed to select a cache line to be replaced after a cache miss. This is because statistical data have shown that for low associativity caches (caches that are configured as four-way set associative or less), an LRU type of replacement scheme can best minimize the cache miss ratio when compared to other cache replacement schemes such as random replacement or round-robin.
It is difficult to implement an LRU cache line replacement mechanism for a multi-port cache memory because the updating algorithm must be able to take into account all concurrent cache requests as well as the current state of the LRU cache line. The present disclosure provides an apparatus for implementing an LRU cache line replacement scheme in a multi-port cache memory within a data processing system.